package pri.zjy.statck;

import java.util.*;

/**
 * @author zhangjy
 * @description 用队列实现栈 法二：入栈直接入，出栈通过队列实现FILO（法1、2其实是同一类型方法，不过Queue的底层实现不同）
 * @date 2025/3/6 10:19
 */
public class MyStack_225_2 {

    public static void main(String[] args) {
        MyStack_225_2 myStack225 = new MyStack_225_2();
        myStack225.push(1);
        myStack225.push(2);
        System.out.println(myStack225.top()); // 返回 2
        System.out.println(myStack225.pop()); // 返回 2
        System.out.println(myStack225.empty()); // 返回 False

    }

    Queue<Integer> in = new LinkedList<>();
    Queue<Integer> out = new LinkedList<>();

    int inSize = 0;
    int outSize = 0;

    public MyStack_225_2() {
    }

    public void push(int x) {
        // 入栈直接入
        // 出栈时，通过队列实现
        in.offer(x);
        inSize++;
    }

    public int pop() {
        // 1.弹出in的元素存到out，直到in剩最后一个
        inToOut();

        // 2.弹出in最后一个元素，并记录
        Integer poll = in.poll();
        inSize--;

        // 3.交换in、out
        switchQueue();

        return poll;
    }

    public int top() {
        // 1.弹出in的元素存到out，直到in剩最后一个
        inToOut();

        // 2.弹出in最后一个元素，并记录
        Integer poll = in.poll();

        // 3.该元素入队out
        out.offer(poll);
        outSize++;

        // 4.交换
        in = out;
        out = new LinkedList<>();
        inSize = outSize;
        outSize = 0;

        return poll;
    }

    public boolean empty() {
        return in.isEmpty();
    }

    private void switchQueue() {
        in = out;
        out = new LinkedList<>();
        inSize = outSize;
        outSize = 0;
    }

    private void inToOut() {
        // 弹出in的元素存到out，直到in剩最后一个
        while (inSize - 1 > 0) {
            out.offer(in.poll());
            inSize--;
            outSize++;
        }
    }

}
